\documentclass[12pt]{article} % default is 10 pt
\usepackage[english]{babel} 
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{color}
\usepackage{xcolor}
\usepackage{listings}

\usepackage{caption}
\DeclareCaptionFont{white}{\color{white}}
\DeclareCaptionFormat{listing}{\colorbox{gray}{\parbox{\textwidth}{#1#2#3}}}
\captionsetup[lstlisting]{format=listing,labelfont=white,textfont=white}

\title{TDDD56 Lab1 - Load Balancing}
\author{Johan Nilsson (johni592), Tobias Pettersson (tobpe416)}
\date{\today}

\addtolength{\voffset}{-0.3in}
\addtolength{\textheight}{50pt}

\begin{document}
\maketitle
\begin{figure}[h!]
   	\includegraphics[scale=0.8]{pics/mandelbrot.png}
	\centering  
\end{figure}
\thispagestyle{empty}
\newpage
\setcounter{page}{1}
\setlength{\parindent}{0in}

\section{Introduction}
This lab is about implementing the computation of the mandelbrot set in parallel, using pthreads. A proposed sequential solution is going to be parallelized. The implemented solution will then be modified in such way that it becomes more load balanced.

\section{Background}
The initial algorithm divides the picture into equal pieces.Assume the average calculation time of each pixel is equal then the relative speedup (see equation \ref{eq:rel_speed}) and relative efficiency (see equation \ref{eq:rel_eff}) can be calculated in the following way: 
% Relative speedup
\begin{align}
  \label{eq:rel_speed}
  S_{p} = \frac{T_{1}}{T_{p}} = p
\end{align}
% Efficiency
\begin{align}
  \label{eq:rel_eff}
  E_{p} = \frac{S_{p}}{p} = 1
\end{align}
The different terms in the expressions can be see in the list below.
\begin{itemize}
\item $p$ is the number of processors
\item $S_{p}$ is the relative speedup
\item $E_{p}$ is the relative efficiency
\item $T_{1}$ is the execution time for the parallel implementation with 1 thread.
\item $T_{p}$ is the execution time for the parallel implementation with p threads.
\end{itemize}
In the calculations the overhead for managing threads and the sequential parts of the program has been ignored. In the lab-computer there is four cores available which means that the theoretical relative speedup can be at maximum $4$ while the theoretical efficiency can be $1$ when the thread count is between $1$ and $4$.

\section{Implementation}

\subsection{Unbalanced implementation}
The image was divided in \# of threads parts of equal size. The first $HEIGHT/ \# of threads$ rows in the image was assigned to thread one and the next $HEIGHT/ \# of threads$ rows and so on. The load balance between the threads became very bad as seen in section \ref{subsec:initial_impl}.

\subsection{Balanced parallel program}
The rows in the image was assigned to the different threads according to the illustration in figure \ref{fig:balanced_impl}. This implementation will have a better load balance becase neighboring row takes approximatly the same time to calculate. In this implementation the black parts of the picture takes the most time to calculate. This sections will now be almost equally distributed between the threads. The load balancing is static, because it is predefined which rows that each thread will calculate.
% balanced program
\begin{figure}[h!]
   	\includegraphics[scale=0.3]{pics/balanced_impl.png}
	\centering
  	\caption{Illustration of the execution (3 threads)}
	\label{fig:balanced_impl}
\end{figure}

\section{Experimental Setup}
The start and stop time and the global execution time for each thread was captured with the {\it clock\_gettime} function. This method uses the clock {\it CLOCK\_MONOTONIC} to measure time at a specific point. {\it CLOCK\_MONOTONIC} represents time since some unspecified starting point. To e.g. get the global execution time you need to subtract the start time and stoptime of the {\it clock\_gettime} function.
\\\\
There is a bash script {\it lab1}, to compile and run the program with 0 to 8 threads. If an extra argument with value 1 is provided then the balanced version is executed otherwise the unbalanced version is executed. The graphs in section \ref{sec:results} is then produced with the matlab script {\it lab1.m}.

\section{Results}
\label{sec:results}
To get reliable execution time for the calculations 20 simulations has been made for the balanced and unbalanced version. The standard deviation for all measurements has also been calculated.
\\\\
As seen in section \ref{subsec:initial_impl} and \ref{subsec:balanced_impl} the results for the global computation time is constant when the number of threads is larger than $4$. This is expected because the number of cores is four which means that the performance shouldn't get better results if you have more than $4$ threads (ignores cache effects and other deviations). As seen in the figures the speedup of the global computation time is not optimal. The reason for this is that there are sequential parts of the code and both the unbalanced and balanced implementation are not perfectly balanced.
\subsection{Initial implementation}
\label{subsec:initial_impl}
The global computation time for the initial implementation can be seen in figure \ref{fig:un_global_time} and the time per thread time can be seen in figure \ref{fig:un_time_per_thread}.
% Result global time from unbalanced impl.
\begin{figure}[h!]
   	\includegraphics[scale=0.5]{pics/un_global_time2.pdf}
	\centering
  	\caption{Global computation time of unbalanced implementation}
	\label{fig:un_global_time}
\end{figure}

% Computation time per thread for unbalanced impl
\begin{figure}[h!]
   	\includegraphics[scale=0.7]{pics/un_time_per_thread2.pdf}
	\centering
  	\caption{Time per thread for unbalanced implementation}
	\label{fig:un_time_per_thread}
\end{figure}
The results in figure \ref{fig:un_time_per_thread} show that the load balance between the threads are in some cases very bad. This is because parts (the black parts) of the image is more computational expensive. That is why the global computation time in cases with odd number of threads do not follow the curve. Many of the rows in the middle of the image are almost completely black and the thread responsible for calculating these rows is a bottleneck.This limits the global computaion time.
\clearpage
\subsection{Load balanced implementation}
\label{subsec:balanced_impl}
The global computation time for the initial implementation can be seen in figure \ref{fig:balanced_global_time} and the time per thread time can be seen in figure \ref{fig:balanced_time_per_thread}. The execution time of the implementation scales well and the maximum absolute speedup is around $2.6$. With 4 cores this is a good result. The load balancing in this implementation is a lot better compared to the unbalanced version. 
% Result global time from balanced impl.
\begin{figure}[h!]
   	\includegraphics[scale=0.5]{pics/balanced_global_time2.pdf}
	\centering
  	\caption{Global computation time of balanced implementation}
	\label{fig:balanced_global_time}
\end{figure}

% Computation time per thread for unbalanced impl
\begin{figure}[h!]
   	\includegraphics[scale=0.7]{pics/balanced_time_per_thread2.pdf}
	\centering
  	\caption{Time per thread for balanced implementation}
	\label{fig:balanced_time_per_thread}
\end{figure}
\clearpage
\section{Conclusion}
As you can see in figure \ref{fig:un_global_time}, \ref{fig:un_time_per_thread}, \ref{fig:balanced_global_time} and \ref{fig:balanced_time_per_thread} a more load balanced implementation leads to better execution time, which is quite obvious because the threads are more utilized. To get an even better load balance you could have a task pool consisting of the different rows to be computed. Every thread will ask for one task, execute it and ask for a new one. The drawback with this method is that you have to introduce for example mutex locks.  
\\\\
This lab was a nice startup lab for this course and was quite easy. We both got a nice repetition in pthreads. The implementation was quite easy and did not take a lot of time and the time for simulation and testing was the most time consuming. The provided script was hard to understand and it was not adapted fully to matlab. 
\end{document}





